package com.azure.code.tree;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * 341 扁平化嵌套列表迭代器
 * [[1,[1]],2,[1,1] ==> flat [1,1,2,1,1]
 */
public class Flatten_NestedInter_341 {
    public interface NestedInteger{
        // 如果其中存在一个整数，则返回 true, 否则返回false
        public boolean isInteger();
        // 如果其中存在的是一个整数，则返回这个整数，否则返回 null
        public Integer getInteger();
        // 如果其中存在的是一个列表，则返回这个列表，否则返回 null
        public List<NestedInteger> getList();
    }
    public class NestedIterator implements Iterator<Integer> {
        private Iterator<Integer> it;
        // 构造  遍历多叉树
        public NestedIterator(List<NestedInteger> nestedList) {
           // 存放将 nestedList 打平的结果
           List<Integer> result = new LinkedList<>();
            for (NestedInteger node : nestedList) {
                // 以每个节点为根节点
                traverse(node,result);
            }
            // 得到result 列表的迭代器
            this.it = result.iterator();
        }

        private void traverse(NestedInteger root, List<Integer> result) {
            if(root.isInteger()){
                // 到达叶子节点
                result.add(root.getInteger());
                return;
            }
            // 遍历每个叶子节点
            for (NestedInteger child : root.getList()) {
                traverse(child,result);
            }
        }

        @Override
        public Integer next() {
            return it.next();
        }

        @Override
        public boolean hasNext() {
            return it.hasNext();
        }
    }


    public class NestedIterator2 implements Iterator<Integer> {
        private LinkedList<NestedInteger> list;
        // 构造  遍历多叉树
        public NestedIterator2(List<NestedInteger> nestedList) {
            // 不直接用 nestedList的引用，是因为不能确定它的底层实现
            // 必须保证是LinkedList，否则下面的addFirst会很低效
          list = new LinkedList<>(nestedList);
        }
        @Override
        public Integer next() {
            // hasNext 方法保证了第一个元素一定是整数类型
            return list.remove(0).getInteger();
        }

        @Override
        public boolean hasNext() {
            // 循环拆分列表元素，直到列表第一个元素是整数类型
            while (!list.isEmpty()&&!list.get(0).isInteger()){
                // 当列表开头第一个元素是列表类型时，进入循环
                List<NestedInteger> first = list.remove(0).getList();
                // 将第一个列表打平并按照顺序添加到开头
                for (int i = first.size()-1; i >=0 ; i--) {
                    list.addFirst(first.get(i));
                }
            }
            return !list.isEmpty();
        }
    }

}
